Associative memories, also referred to as content addressable memories, are widely used in the field of pattern matching and identification, expert systems and artificial intelligence. A widely used associative memory is the Hopfield artificial neural network. Hopfield artificial neural networks are described, for example U.S. Pat. No. 4,660,166 to Hopfield entitled "Electronic Network for Collective Decision Based on Large Number of Connections Between Signals".
In general, a Hopfield artificial neural network comprises a plurality of artificial neurons, also referred to as nodes. One artificial neuron is generally provided for each input line of an input vector. One-to-one connections are provided between all artificial neurons. For a set of input attributes such as {A, B, C}, input vectors such as [101] or [100] may be loaded into the neural network. The neural network representation is found on the weights of the arcs between the neurons. These weights are initialized to 0. A storage prescription formula generally operates as follows: if both input bits of the corresponding nodes are the same, the weight is incremented by 1. Otherwise, the input bits are different and the weight is decremented by 1. This formula creates a memory with similarities to an Ising spin model from physics, in which given the spins of an array of electrons, there are stable states that the system will relax to if the electrons are allowed to toggle. The storage formula causes the network to store the loaded cases as such stable states, or attractors.
An important use of Hopfield networks is for autoassociative recall. That is, once a number of input vectors have been loaded or written as attractors into such a memory, a new vector can be clamped to the nodes, and by the following procedure, a loaded memory can be recalled or read from a partial or corrupted memory. Each node calculates the dot product of all other connected node's bipolar states and the respective connection weights. Specifically, each arc's weight is multiplied by +1 if the input bit is on or by -1 if off, and all these products are summed. Asynchronously, each node flips itself on if this dot product is positive or off if it is negative. Given a new case as an input vector, this procedure will change the bit patterns until the memory "relaxes" to an attractor, usually representing one of the loaded memories or a prototype of several memories. For instance, when loaded with several examples of handwritten `O's, such a memory will tend to report the prototype `O` if given any new, partial, or corrupted shape close to an `O`.
Hopfield networks are widely used and are available in many commercial neural network packages. However, their application may be limited by their poor capacity. Very large virtual machines, up to 1000 bits and more, have been built, but in practice, these memories appear capable of only 0.15N attractors. The theoretical limit is 2N.
Another important limitation in Hopfield neural networks is spurious memories. If the new vector is close enough to a loaded memory, then the relaxation technique will recall the loaded memory based on the new vector. In mathematical terms, if the Hamming distance (sum of binary differences) between the new vector and the address of the attractor are close enough relative to the size of the entire Boolean space, then Hopfield networks work appropriately. Unfortunately, however, the storage prescription formula may also cause spurious attractors--false memories--to be created in the weight space as well.
The creation of spurious memories in a neural network may be illustrated by the following example. Although Hopfield networks may be best illustrated in very large networks, the basic problem of spurious memories can be seen with only three neurons. Consider the input set {A, B, C} and the ordered input vector [111]. The prescription formula would load this vector so that weight.sub.AB =weight.sub.AC =weight.sub.BC =+1.
Reading this loaded case from a new case such as [110] may be performed without spurious error. From the perspective of the A node, the dot product=0. A makes no change. The same is true for the B node. However, the C nodes dot product is (1*1+1*1)=+2. While the given input bit is off, this dot product means that it should be on. Flipping C ON relaxes the network in the sense that all dot products are positive and all bits are ON, as they should be according to the loaded memory.
However, if the vector [000] is input, the dot products are all negative and the bits all off. This is a stable-state attractor (the vector [001] will move to it too). However, it is spurious because it was never loaded as an actual case.
Although it may be difficult to provide a perfect associative memory that is tractable to large space unless P=NP, a spurious memory as illustrated above may be particularly problematic. Specifically, some reasonable (and maybe even "good") error may be expected in associative memories, but such unreasonable memories are troublesome. In general, Hopfield networks tend to spurious attractors that are the compliment of the intended attractors. In this case, the intended attractor at [111] also produced a spurious attractor at [000]. Thus, an input that is opposite to the intended input will also give a positive result. Spurious complement memories may be particularly troublesome for pattern matching, artificial intelligence and other applications of neural networks.